package q918_maxSubarraySumCircular;

public class Solution {
    /*
    此题首先需要回顾53题，动态规划的过程中寻找最大和的子数组
    但是需要考虑的是 如果最大和的子数组包含了首尾连接的两个数 应该如何表示
    那么此时可以通过考虑数学问题：
    如果将数组看为一个环 那么环可以由两个任意数组构成
    如果其中有一个数组是最大和数组，那么此时剩下的一个数组一定是最小和数组
    这也不难证明 因为显然在一个固定的总和下面 一段达到了最大值 那么另一段一定是最小值

    因此 我们用同样的方法维护一个最小和数组 最后判断时考虑
    如果实际max没有穿过环 那么Math.max(maxSum, total - minSum)应该是会返回maxSum的
    如果穿过了环 代表此时维护的另一个minSum应该到最小值了 因此返回total - minSum
     */
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0, maxSum = nums[0], curMax = 0, minSum = nums[0], curMin = 0;
        for (int a : nums) {
            curMax = Math.max(curMax + a, a);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + a, a);
            minSum = Math.min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}
